import java.util.Arrays;

/**
 * 135. 分发糖果
 * https://leetcode-cn.com/problems/candy/
 */
public class Solutions_135 {
    public static void main(String[] args) {
//        int[] nums = {1, 0, 2};  // output: 5
//        解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

        int[] nums = {1, 2, 3, 5, 4, 3, 2, 1};
        // output: 1 + 2 + 3 + 5 + 4 + 3 + 2 + 1 = 21

//        int[] nums = {1, 2, 2};  // output: 4
//        解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
//        第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

        int result = candy(nums);
        System.out.println(result);
    }

    /**
     * 解题思路：两遍扫描，正序与逆序
     */
    public static int candy(int[] ratings) {
        int len = ratings.length;
        // rating[1] = 2，表示给第 2 个孩子，2 个糖果
        int[] res = new int[len];
        // 每个孩子最少 1 个糖果
        Arrays.fill(res, 1);

        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1]) {
                // 表现比前一个好时，那么糖果比前一个多
                res[i] = res[i - 1] + 1;
            }
        }
        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                // 表现比后一个好时，那么糖果比后一个多
                // 但是需要比较最大值，因为可能既比前面表现好，也比后面表现好
                // 而前面一孩子的糖果为 3，后面一孩子的糖果为 4 时，
                // 那么当前孩子的糖果应该是 5
                res[i] = Math.max(res[i], res[i + 1] + 1);
            }
        }
        int sum = 0;
        for (int num : res) {
            sum += num;
        }
        return sum;
    }
}
